/*
 二叉树
 */

#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
 
using namespace std;
using std :: vector;


class TreeNode{
public:
    int value;
    TreeNode *left, *right;
    TreeNode(int val){
        this->value = val;
        this->left = this->right = NULL;
    }
    
    vector<int>vec;
#pragma mark - 前序遍历(根 左 右)
    vector<int> preorderTraversal(TreeNode *root){
        if (root == NULL) {
            return vec;
        }
        vec.push_back(root->value);
        
        if (root->left != NULL) {
            preorderTraversal(root->left);
        }
        if (root->right != NULL) {
            preorderTraversal(root->right);
        }
        
        return vec;
    }
    
#pragma mark - 中序 (左 根 右)
    vector<int> midOrder(TreeNode *root){
        if (root == NULL) {
            return vec;
        }
        if (root->left) {
            backOrder(root->left);
        }
        
        vec.push_back(root->value);
        
        if (root->right) {
            backOrder(root->right);
        }
        return vec;
    }
    
#pragma mark - 后序 (左 右 根)
    vector<int> backOrder(TreeNode *root){
        if (root == NULL) {
            return vec;
        }
        if (root->left) {
            backOrder(root->left);
        }
        if (root->right) {
            backOrder(root->right);
        }
        
        vec.push_back(root->value);
        
        return vec;
    }
    
    
#pragma mark - 层序遍历
    
    vector<vector<int>> layerOrder(TreeNode *root){
        vector<vector<int>> tree;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {//
            vector<int> layer;
            for (int i  = 0; i<q.size(); i++) {//一个for循环是一层
                TreeNode *node = q.front();
                q.pop();
                layer.push_back(node->value);
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
                
            }
           
            tree.push_back(layer);
        }
        
        return tree;
    }
    
#pragma mark - 给定一个二叉树，找出其最大深度。
    int maxDepth(TreeNode *root){
        if (root == NULL) {
            return 0;
        }
        
        int left = maxDepth(root->left);//一路向左
        int righ = maxDepth(root->right);
        
        return 1 + (left>righ?left:righ);
    }
    
#pragma mark - 找出最小深度
    //1.递归
    //2.分层遍历? (借助队列, 每一层的个数是2^n-1次方)
    int minDepth(TreeNode *root){
        if (root == NULL) {
            return 0;
        }
        
        if (root->left == NULL) {//需要考虑单边子树情况(如:只有一边)
            return minDepth(root->right) + 1;
        }
        if (root->right == NULL) {
            return minDepth(root->left) + 1;
        }
        int left = minDepth(root->left);
        int right = minDepth(root->right);
        
        return (left<right?left:right) + 1;
    }
    
#pragma mark - 翻转一棵二叉树。左右子树交换。
    void inverseTree_1(TreeNode *root){
        if (root == NULL) {
            return;
        }
        TreeNode *node = root->left;
        root->left = root->right;
        root->right = node;
        inverseTree_1(root->left);
        inverseTree_1(root->right);
        
    }
    
    TreeNode *inverseTree_2(TreeNode *root){
        if (root == NULL) {
            return NULL;
        }
        root->left = inverseTree_2(root->left);
        root->right = inverseTree_2(root->right);
        
        TreeNode *temp = root->left;
        root->left = root->right;
        root->right = temp;
        return root;
    }
    
    
    
};
